/**
 * [79] 单词搜索
 * 思路：
 * 1 逐行扫描，寻找首字母
 * 2 上下左右，寻找下一字母，判断：未越界&未使用&目标字符
 * 3
 * # 用二进制字符串 isUsed 记录每个网格元素是否已被使用，|1置1 &0置0（回溯时）
 * # 外层循环 m*n 次
 * # 变量 i,j 记录首字母行列索引，x,y 记录当前节点字符坐标，k 记录当前节点字符索引
 * # 当 len == word.length 返回 true
 * @format
 * @lc app=leetcode.cn id=79 lang=javascript
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    // L：单词长度，MN：网格宽高（M 行 N 列）
    const [L, M, N] = [word.length, board.length, board[0].length]
    // 上右下左坐标偏移
    const offset = [
        { x: 0, y: -1 },
        { x: 1, y: 0 },
        { x: 0, y: 1 },
        { x: -1, y: 0 }
    ]
    // 行列索引
    let i = 0
    while (i < M) {
        let j = 0
        while (j < N) {
            if (board[i][j] === word[0]) {
                // 对应二进制位记录是否已使用
                // let isUsed = 2 ** (i * N + j)
                const isUsed = Array(M)
                    .fill(0)
                    .map(() => Array(N).fill(0))
                // 备忘录，记录 memo[k] 对应 word[k] 字符（已使用）坐标
                const memo = [{ x: j, y: i, o: 0 }]
                isUsed[i][j] = 1
                let k = 0
                while (k < L) {
                    if (memo.length == L) return true
                    while (memo[k].o < 4) {
                        let [x, y] = [
                            memo[k].x + offset[memo[k].o].x,
                            memo[k].y + offset[memo[k].o].y
                        ]
                        // const isNotUsed = !(isUsed & (2 ** (y * N + x)))
                        const isTarget = board[y] && board[y][x] === word[k + 1] && !isUsed[y][x]
                        if (isTarget) {
                            memo.push({ x, y, o: 0 })
                            // isUsed = isUsed | (2 ** (y * N + x))
                            isUsed[y][x] = 1
                            memo[k].o++
                            k++
                            break
                        } else {
                            memo[k].o++
                        }
                    }
                    if (memo[k].o == 4) {
                        // isUsed = isUsed & ~(2 ** (memo[k].y * N + memo[k].x))
                        isUsed[memo[k].y][memo[k].x] = 0
                        memo.pop()
                        k--
                    }
                    if (k < 0) break
                }
            }
            j++
        }
        i++
    }
    return false
}
debugger
const board = [["a", "a"]]
const word = "aaa"
console.log(exist(board, word))
// @lc code=end
